<?php
/* Driver template for the LEMON parser generator.
** The author disclaims copyright to this source code.
*/

/* Next is all token values, in a form suitable for use by makeheaders.
** This section will be null unless lemon is run with the -m switch.
*/
/* 
** These constants (all generated automatically by the parser generator)
** specify the various kinds of tokens (terminals) that the parser
** understands. 
**
** Each symbol here is a terminal symbol in the grammar.
*/
%%

/*
** This class is used for all minor tokens.
*/
%%


/* The following class represents a single element of the
** parser's stack.  Information stored includes:
**
**   +  The state number for the parser at this level of the stack.
**
**   +  The value of the token stored at this level of the stack.
**      (In other words, the "major" token.)
**
**   +  The semantic value stored at this level of the stack.  This is
**      the information used by the action routines in the grammar.
**      It is sometimes called the "minor" token.
*/
class Parse_StackEntry {
	/**
	 * @var int $stateno The state-number
	 */
	public $stateno;
	
	/**
	 * @var int $major The major token value.  
	 *
	 * This is the code number for the token at this stack level 
	 */
	public $major;     
	
	/**
	 * @var Parse_Minor $minor The user-supplied minor token value.
	 *
	 * This is the value of the token
     */
	public $minor;
	
	function Parse_StackEntry() {
		$this->minor = new Parse_Minor();
		$this->stateno = 0;
		$this->major = 0;
	}
		
}

class Parse_Stack {

	private $stack;
	
	function Parse_Stack() {
		$this->stack = array();
	}
	
	/**
	 * Returns the top of this stack
	 *
	 * @return Parse_StackEntry
	 */
	function getTop() {
		return $this->stack[count($this->stack) - 1];
	}
	
	function getBottom() {
		return $this->stack[0];
	}
	
	function getRelative($offset = 0) {
		$i = count($this->stack) - 1;
		return $this->stack[$i + $offset];
	}
	
	/**
	 * Pops elements from the stack
	 *
	 * @param int $i number of elements to pop
	 * @return Parse_StackEntry last popped element
	 */
	function pop($i = 1) {
		for ($x = 0; $x < $i; $x++)
			array_pop($this->stack);	
	}
	
	function push(Parse_StackEntry $entry) {
		array_push($this->stack, $entry);
	}
	
	function size() {
		return count($this->stack);
	}
	
	function getArray() {
		return $this->stack;
	}
}

class Parse {
	
	/* Code is include which follows the "include" declaration
	** in the input file. */
%%

	private $stack;
	private $yyerrcnt;
	
	/* The next thing included is series of constants which control
	** various aspects of the generated parser.
	**    YYNOCODE           is a number which corresponds to no legal terminal
	**                       or nonterminal number.  This number is used to 
	**                       fill in empty slots of the hash table.
	**    YYFALLBACK         If defined, this indicates that one or more tokens
	**                       have fall-back values which should be used if the
	**                       original value of the token will not parse.
	**    YYSTACKDEPTH       is the maximum depth of the parser's stack.
	**    YYNSTATE           the combined number of states.
	**    YYNRULE            the number of rules in the grammar
	**    YYERRORSYMBOL      is the code number of the error symbol.  If not
	**                       defined, then do no error processing.
	*/
%%

	private $yyRuleInfo = array(
		// array(LHS, NRHS)
%%		
	);
	
	/* Next are that tables used to determine what action to take based on the
	** current state and lookahead token.  These tables are used to implement
	** functions that take a state number and lookahead value and return an
	** action integer.  
	**
	** Suppose the action integer is N.  Then the action is determined as
	** follows
	**
	**   0 <= N < YYNSTATE                  Shift N.  That is, push the lookahead
	**                                      token onto the stack and goto state N.
	**
	**   YYNSTATE <= N < YYNSTATE+YYNRULE   Reduce by rule N-YYNSTATE.
	**
	**   N == YYNSTATE+YYNRULE              A syntax error has occurred.
	**
	**   N == YYNSTATE+YYNRULE+1            The parser accepts its input.
	**
	**   N == YYNSTATE+YYNRULE+2            No such action.  Denotes unused
	**                                      slots in the yy_action[] table.
	**
	** The action table is constructed as a single large table named yy_action[].
	** Given state S and lookahead X, the action is computed as
	**
	**      yy_action[ yy_shift_ofst[S] + X ]
	**
	** If the index value yy_shift_ofst[S]+X is out of range or if the value
	** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X or if yy_shift_ofst[S]
	** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table
	** and that yy_default[S] should be used instead.  
	**
	** The formula above is for computing the action when the lookahead is
	** a terminal symbol.  If the lookahead is a non-terminal (as occurs after
	** a reduce action) then the yy_reduce_ofst[] array is used in place of
	** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of
	** YY_SHIFT_USE_DFLT.
	**
	** The following are the tables generated in this section:
	**
	**  yy_action[]        A single table containing all actions.
	**  yy_lookahead[]     A table containing the lookahead for each entry in
	**                     yy_action.  Used to detect hash collisions.
	**  yy_shift_ofst[]    For each state, the offset into yy_action for
	**                     shifting terminals.
	**  yy_reduce_ofst[]   For each state, the offset into yy_action for
	**                     shifting non-terminals after a reduce.
	**  yy_default[]       Default action for each state.
	*/
%%
	
	/* The next table maps tokens into fallback tokens.  If a construct
	** like the following:
	** 
	**      %fallback ID X Y Z.
	**
	** appears in the grammer, then ID becomes a fallback token for X, Y,
	** and Z.  Whenever one of the tokens X, Y, or Z is input to the parser
	** but it does not parse, the type of the token is changed to ID and
	** the parse is retried before an error is thrown.
	*/
	private $yyFallback = array(
		#INCLUDE GENERATED
%%
		#END
	);
	
	function __construct() {
		$this->stack = new Parse_Stack();		
		$this->yyerrcnt = -1;
	}
	
	/* The following function deletes the value associated with a
	** symbol.  The symbol can be either a terminal or nonterminal.
	** "yymajor" is the symbol code, and "yypminor" is a pointer to
	** the value.
	*/
	private function yy_destructor($yymajor, $yypminor) {
		switch ($yymajor) {
			/* Here is inserted the actions which take place when a
			** terminal or non-terminal is destroyed.  This can happen
			** when the symbol is popped from the stack during a
			** reduce or during error processing or when a parser is 
			** being destroyed before it is finished parsing.
			**
			** Note: during a reduce, the only symbols destroyed are those
			** which appear on the RHS of the rule, but which are not used
			** inside the C code.
			*/
			#INCLUDE GENERATED
%%
			default:  break;   /* If no destructor action specified: do nothing */
			#END
		}
	}
	
	/**
	 * Pop the parser's stack once.
	 *
	 * If there is a destructor routine associated with the token which
	 * is popped from the stack, then call it.
	 *
	 * @return int The major token number for the symbol popped.
	 */
	private function yy_pop_parser_stack() {
		$yytos = $this->stack->getTop();
		
		// if no items on the stack
		if (! $this->stack->size()) return 0;
		
		if (defined('DEBUG')) {
			echo "Popping " . $this->getSymbolName($yytos->major) . "\n";
		}
		
		$yymajor = $yytos->major;
		$this->yy_destructor($yymajor, $yytos->minor);
		
		$this->stack->pop();
		
		return $yymajor;
	}
	
	/**
	 * Find the appropriate action for a parser given the terminal
	 * look-ahead token iLookAhead.
	 *
	 * If the look-ahead token is YYNOCODE, then check to see if the action is
	 * independent of the look-ahead.  If it is, return the action, otherwise
	 * return YY_NO_ACTION.
	 *
	 * @param int $iLookAhead Look-ahead token
	 * @return int Number of the action to perform
	 */
	private function yy_find_shift_action($iLookAhead) {
		$stateno = $this->stack->getTop()->stateno;
		
		/* if (! $this->stack->size()) return YY_NO_ACTION;  */
		$i = $this->yy_shift_ofst[$stateno];
	  
		if ($i == self::YY_SHIFT_USE_DFLT)
			return $this->yy_default[$stateno];
	  
		if ($iLookAhead == self::YYNOCODE)
			return self::YY_NO_ACTION;
			
		$i += $iLookAhead;
		
		if ($i < 0 || $i >= count($this->yy_action) || $this->yy_lookahead[$i] != $iLookAhead) {
			if (self::YYFALLBACK) {
				// int iFallback;            /* Fallback token */
				
				if ($iLookAhead < count($this->yyFallback)
					&& ($iFallback = $this->yyFallback[$iLookAhead]) != 0) {
						
					if (defined('DEBUG')) {
						printf("FALLBACK %s => %s\n"
							,$this->getSymbolName($iLookAhead)
							,$this->getSymbolName($iFallback));
					
					}
					
					return $this->yy_find_shift_action($iFallback);
				}
			}
				
			return $this->yy_default[$stateno];
		} else {
			return $this->yy_action[$i];
		}
	}
	
	/**
	 * Find reduce action
	 *
	 * Find the appropriate action for a parser given the non-terminal
	 * look-ahead token iLookAhead.
	 *
	 * If the look-ahead token is YYNOCODE, then check to see if the action is
	 * independent of the look-ahead.  If it is, return the action, otherwise
	 * return YY_NO_ACTION.
	 *
	 * @param int $stateno Current state number 
	 * @return int The look-ahead token
	 */
	private function yy_find_reduce_action($stateno, $iLookAhead) {
		
		$i = $this->yy_reduce_ofst[$stateno];
		if ($i == self::YY_REDUCE_USE_DFLT)
			return $this->yy_default[$stateno];
		
		if ($iLookAhead == self::YYNOCODE)
			return self::YY_NO_ACTION;
		
		
		$i += $iLookAhead;
		
		if ($i < 0 || $i >= count($this->yy_action) || $this->yy_lookahead[$i] != $iLookAhead) {
			return $this->yy_default[$stateno];
		} else {
			return $this->yy_action[$i];
		}	
	}
	
	/**
	 * Perform a shift action.
	 *
	 * @param int $yyNewState The new state to shift in
	 * @param int $yyMajor The major token to shift in
	 * @param $yypMinor Pointer t0 the minor token to shift in
	 */
	private function yy_shift($yyNewState, $yyMajor, $yypMinor) {
				
		if ($this->stack->size() + 1 >= self::YYSTACKDEPTH) {
			if (defined('DEBUG')) {
				printf("Stack Overflow!\n");
			}
			
			while ($this->stack->size()) $this->yy_pop_parser_stack();
			
			// Here code is inserted which will execute if the parser
			// stack every overflows
%%
			return;
		}
		
		$yytos = new Parse_StackEntry();
		$yytos->stateno = $yyNewState;
		$yytos->major = $yyMajor;
		$yytos->minor = $yypMinor;
		$this->stack->push($yytos);
		
		if (defined('DEBUG')) {
			printf("Shift %d\n", $yyNewState);
			printf("Stack:");
			
			$stack = $this->stack->getArray();
			for ($i = 1; $i < count($stack); $i++)
				printf(" %s", $this->getSymbolName($stack[$i]->major));
				
	    	printf("\n");
	    }
	}
	
	/**
	 * Reduce action
	 *
	 * Perform a reduce action and the shift that must immediately
	 * follow the reduce.
	 *
	 * @param int $yyruleno Number ot hte rule by which to reduce
	 */
	private function yy_reduce($yyruleno) {
		
		$yygotominor = new Parse_Minor();         /* The LHS of the rule reduced */
		
		$stack = $this->stack;
		
		if (defined('DEBUG')) {
			printf("Reduce [%s].\n", $this->getRuleName($yyruleno));
		}
		
		switch ($yyruleno) {
			/* Beginning here are the reduction cases.  A typical example
			** follows:
			**   case 0:
			**  #line <lineno> <grammarfile>
			**     { ... }           // User supplied code
			**  #line <lineno> <thisfile>
			**     break;
			*/
%%
		}
		
		$rule = $this->yyRuleInfo[$yyruleno];
		$yygoto = $rule[0];
		$yysize = $rule[1];
		
		// find next action
		$yyact = $this->yy_find_reduce_action($stack->getRelative(-$yysize)->stateno, $yygoto);
		
		$this->stack->pop($yysize);
		
		if ($yyact < self::YYNSTATE) {
			if (! defined('DEBUG')) {
				/* If we are not debugging and the reduce action popped at least
				** one element off the stack, then we can push the new element back
				** onto the stack here, and skip the stack overflow test in yy_shift().
				** That gives a significant speed improvement. */
				
				if ($yysize) {
					$yymsp = new Parse_StackEntry();
					$yymsp->stateno = $yyact;
					$yymsp->major = $yygoto;
					$yymsp->minor = $yygotominor;
					$this->stack->push($yymsp);
					
				} else {
					$this->yy_shift($yyact, $yygoto, $yygotominor);
				}
			} else {
				$this->yy_shift($yyact, $yygoto, $yygotominor);
			}
		} else if($yyact == self::YY_ACCEPT_ACTION) {
			$this->yy_accept();
		}
	}
	
	/**
	 * The following code executes when the parse fails
	 */
	private function yy_parse_failed() {
		
		if (defined('DEBUG')) {
			printf("Fail!\n");
		}
		
		while ($this->stack->size()) $this->yy_pop_parser_stack();
		
		// Here code is inserted which will be executed whenever the
		// parser fails
%%
		
	}
	
	/**
	 * The following code executes when a syntax error first occurs.
	 *
	 * @param int $yymajor The major type of the error token
	 * @param $yyminor The minor type of the error token
	 */
	private function yy_syntax_error($yymajor, $yyminor) {
%%
	}
	
	/**
	 * The following is executed when the parser accepts
	 */
	private function yy_accept() {
		if (defined('DEBUG')) {
			printf("Accept!\n");
	  	}
	  	
	  	while ($this->stack->size()) $this->yy_pop_parser_stack();
	  	
	  	// Here code is inserted which will be executed whenever the
	  	// parser accepts
%%
	}
	
	
	/**
	 * The main parser program.
	 *
	 * The first argument is a pointer to a structure obtained from
	 * "ParseAlloc" which describes the current state of the parser.
	 * The second argument is the major token number.  The third is
	 * the minor token.  The fourth optional argument is whatever the
	 * user wants (and specified in the grammar) and is available for
	 * use by the action routines.
	 *
	 * @param int $yymajor The major token number.
	 * @param $yyminor The minor token number.
	 */
	public function parse($yymajor, $yyminor) {

		$yyminorunion = new Parse_Minor();
		$yyerrorhit = false; // true if yymajor has invoked an error
		
		// (re)initialize the parser, if necessary
		if (! $this->stack->size()) {
			
			if ($yymajor == 0) return;
			
			$this->yyerrcnt = -1;
			$this->stack->push(new Parse_StackEntry());
		}
		
		$yyminorunion->yy0 = $yyminor;
		$yyendofinput = ($yymajor == 0);
		
		if (defined('DEBUG')) {
			printf("Input %s\n", $this->getSymbolName($yymajor));
		}
	
		do {
			$yyact = $this->yy_find_shift_action($yymajor);
			if ($yyact < self::YYNSTATE) {
				$this->yy_shift($yyact, $yymajor, $yyminorunion);
				$this->yyerrcnt--;
				
				if ($yyendofinput && $this->stack->size()) {
					$yymajor = 0;
				} else {
					$yymajor = self::YYNOCODE;
				}
				
			} else if ($yyact < self::YY_ERROR_ACTION) {
				$this->yy_reduce($yyact - self::YYNSTATE);
				
			} else if($yyact == self::YY_ERROR_ACTION) {
				
				if (defined('DEBUG')) {
					printf("Syntax Error!\n");
				}
				
				if (defined(self::YYERRORSYMBOL)) {
					/* A syntax error has occurred.
					** The response to an error depends upon whether or not the
					** grammar defines an error token "ERROR".  
					**
					** This is what we do if the grammar does define ERROR:
					**
					**  * Call the %syntax_error function.
					**
					**  * Begin popping the stack until we enter a state where
					**    it is legal to shift the error symbol, then shift
					**    the error symbol.
					**
					**  * Set the error count to three.
					**
					**  * Begin accepting and shifting new tokens.  No new error
					**    processing will occur until three tokens have been
					**    shifted successfully.
					**
					*/
					
					if ($this->yyerrcnt < 0) {
						$this->yy_syntax_error($yymajor, $yyminorunion);
					}
					
					$yymx = $this->stack->getTop()->major;
					
					if ($yymx == self::YYERRORSYMBOL || $yyerrorhit) {
						if (defined('DEBUG')) {
							printf("Discard input token %s\n", $this->getSymbolName($yymajor));
						}
						
						$this->yy_destructor($yymajor, $yyminorunion);
						$yymajor = self::YYNOCODE;
					} else {
						
						while(
							$this->stack->size()
							&& $yymx != self::YYERRORSYMBOL 
							&& ($yyact = $this->yy_find_shift_action(self::YYERRORSYMBOL)) >= self::YYNSTATE
						) {
							$this->yy_pop_parser_stack();
						}
						
						if (! $this->stack->size() || $yymajor == 0) {
							$this->yy_destructor($yymajor, $yyminorunion);
							$this->yy_parse_failed();
							$yymajor = self::YYNOCODE;
							
						} else if ($yymx != self::YYERRORSYMBOL) {
							
							$u2 = new Parse_Minor();
							$attr = self::YYERRSYMDT;
							$u2->$attr = 0;
							
							$this->yy_shift($yyact, self::YYERRORSYMBOL, $u2);
						}
					}
					
					$this->yyerrcnt = 3;
					$yyerrorhit = true;
					
				} else {  /* YYERRORSYMBOL is not defined */
				
					/* This is what we do if the grammar does not define ERROR:
					**
					**  * Report an error message, and throw away the input token.
					**
					**  * If the input token is $, then fail the parse.
					**
					** As before, subsequent error messages are suppressed until
					** three input tokens have been successfully shifted.
					*/
					
					if ($this->yyerrcnt <= 0) {
						$this->yy_syntax_error($yymajor, $yyminorunion);
					}
					
					$this->yyerrcnt = 3;
					$this->yy_destructor($yymajor, $yyminorunion);
					
					if ($yyendofinput) {
						$this->yy_parse_failed();
					}
	
					$yymajor = self::YYNOCODE;
				}
			} else {
				$this->yy_accept();
				$yymajor = self::YYNOCODE;
			}
		} while ($yymajor != self::YYNOCODE && $this->stack->size());
		
		return;
	}
	
	/** 
	 * Destructors are all called for
	 * all stack elements before shutting the parser down.
	 *
	 */
	public function finalize() {
		while ($this->stack->size()) $this->yy_pop_parser_stack();
	}
	
	/**
	 * Get the name for a symbol
	 *
	 * @param int $i symbol index
	 * @return string Symbol name
	 */
	public function getSymbolName($i) {
		/* For tracing shifts, the names of all terminals and nonterminals
		** are required.  The following table supplies these names */
		$yyTokenName = array(
%%
		);
		
		return $yyTokenName[$i];
	}

	public function getRuleName($i) {
		
		/* For tracing reduce actions, the names of all rules are required.
		*/
		$yyRuleName = array(
%%
		);
		
		return $yyRuleName[$i];
	}
}
?>